模拟赛题解/2025.10.6 模拟赛

T1-开端（bgning）

题面

给定一个长度为 $N$ 的非负整数序列 $A=(a_0,a_1,\dots,a_{N-1})$ 以及两个正整数 $F$ 和 $T$。

一次操作定义为交换序列 $A$ 中任意两个相邻元素 $a_i$ 和 $a_{i+1}$。

求最少的操作次数，使得操作后的序列 $A'$ 满足 $\sum_{i=0}^{F-1} a'_i \ge T$。

$1\leq N\leq100,0\leq F\leq N,0\leq T\leq10^{11},0\leq a_i\leq10^9$。

题解

设 $f_{i,j}$ 表示在选了 $i$ 个数，下标和为 $j$ 的最大和。

于是问题就转化为一个类似背包的问题，最后只需要计算最小的 $j$ 使得 $f_{F,j}\geq T$ 即可，操作次数即为 $j-\frac{(1+F)F}2$。

直接 $O(n)\text{ dp}$ 解决。

T2-发展（dvlpmnt）

题面

给定一个长度为 $n$ 的序列 $a$，你需要从中选出一个元素个数不小于 $\left\lceil\frac{n}{2}\right\rceil$ 的子序列，使得这个子序列中所有元素的 $\gcd$ 最大。

你只需要求出这个最大值即可。

$2\leq n\leq10^5,1\leq a_i\leq10^{12}$。

题解

注意到，因为最终的 $\text{gcd}$ 是至少 $\lceil\frac n2\rceil$ 个数的因数，所以可以考虑直接随机选择一个数。

随机选择 $10$ 次之后，选不到任何一个最终答案的倍数的概率为 $\frac1{1024}$，几乎可以忽略。

于是直接 $O(\sqrt V)$ 枚举所有当前数的因数，并且 $O(n\sqrt V)$ 找到所有数和当前数的 $\text{gcd}$。

最后 $O(k^2)$ 得到所有因数的出现次数（其中 $k$ 为当前数因数个数），从大到小枚举得到的第一个 $\geq \frac n2$ 的值对答案进行一次更新。

复杂度 $O(n\sqrt V+k^2)$。

T3-高潮（climax）

题面

给定一个 $2n$ 行 $m$ 列的棋盘。每个格点被染成红色（R）或蓝色（B），其中红色格点和蓝色格点各占一半，即各有 $nm$ 个。

保证棋盘的左上角格点 $(1,1)$ 为红色，右下角格点 $(2n,m)$ 为蓝色。

将所有红色格点之间两两连边，所有蓝色格点之间两两连边。

你需要判断能否将这些边定向，使得定向后的所有 $nm(nm-1)$ 个有向量之和为 $0$。

请输出任意一种构造方案。如果无解，则输出最小的偶数 $a>2$，满足 $a$ 不能被表示为两个素数之和。

$2\leq n\times m\leq3000$。

题解

注意到，当 $n\times m$ 为奇数的时候，每个点的度数都为偶数，可以直接欧拉回路解决。

当 $n\times m$ 为偶数的时候，每个点的度数为奇数，考虑直接先不去除掉 $(1,1)$ 和 $(2n,m)$，按照 $n\times m$ 为奇数的情况处理。

最后可以发现，只要从 $(1,1)$ 向所有红色点定向，从 $(2n,m)$ 向所有蓝色点定向即可，可以证明向量和一定为 $0$。

复杂度 $O(n^2m^2)$。

T4-结局（cnclusn）

题面

给定两个非负整数 $n,m$ 满足 $0 \le n \le m$。

对于一个长度为 $n$ 的整数序列 $a$，满足 $1 \le a_i \le m$ 且 $a_i$ 互不相同，我们按如下规则定义 $F(a)$：

• 将 $a_i$ 按照从小到大的顺序排序；
• 将序列进行一次差分，记 $a'$ 为差分后的序列 $a_1, a_2-a_1, a_3-a_2, \dots, a_n-a_{n-1}$；
• 将 $a'_i$ 按照从小到大的顺序排序；
• 将 $a'$ 进行一次前缀和，记 $a''$ 为取前缀和后的序列 $a'_1, a'_1+a'_2, a'_1+a'_2+a'_3, \dots, \sum_{k=1}^n a'_k$；
• 定义 $F(a)=a''$。

记 $E_i$ 为当序列 $a$ 在所有 $m!/(m-n)!$ 个满足长度为 $n$ 且 $1 \le a_i \le m$ 且 $a_i$ 互不相同的序列中均匀随机选取时 $F(a)$ 的期望值（即 $F(a)$ 的第 $i$ 个元素的期望值），你需要对于 $1 \le i \le n$ 求出 $E_i$，输出实数结果。

$1\leq n\leq50,n\leq m\leq10000$。

题解

设 $dp[i][j][k]$ 表示如果选择 $i$ 个数，且每个数不超过 $j$ 的前提下，$a''_k$ 的期望是多少。

显然，我们需要要求的即为 $dp[n][m][*]$。

不妨设差分序列内严格大于 $1$ 的元素有 $k$ 个，这种情况出现的概率为 $\frac{\binom{i}{k}\binom{j-i}{k}}{\binom{j}{i}}$。 则对 $0 \le z < k$，我们有转移：

• $dp[i][j][z+i-k] \leftarrow \frac{\binom{i}{k}\binom{j-i}{k}}{\binom{j}{i}} \cdot dp[k][j-i][x]$。

由于本题要求输出实数，因此实现时需要注意精度问题。例如在计算组合数时，应使用递推方式 $\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}$ 来避免精度误差。

复杂度 $O(n^3m)$。